# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from typing import Optional
from tree_node import TreeNode,build_tree_node


class Solution:
    """
    原始方案逻辑大幅简化
    """
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        # 维护的最小值
        result = float('-inf')
        # 深度优先探索
        def dfs(root):
            if not root:
                return 0
            # 对左右子树进行计算，获取其连接根节点的最大值（如果此值为负，则取0）
            left = dfs(root.left)
            right = dfs(root.right)
            nonlocal result
            # 将当前最大值，与当前子树下（过根节点）的最大值进行比较
            result = max(result, left+right+root.val)
            # 将左右较大的dp值与根节点的和，与0的较大值，上传给上一级
            return max(max(left, right)+root.val, 0)
        dfs(root)
        return result